/*************************************************************************
	> File Name: max_heap.cpp
	> Author: 
	> Mail: 
	> Created Time: 五 12/25 15:50:40 2015
 ************************************************************************/

#include<iostream>
#include<cassert>

using namespace std;
template<typename T>
class MaxHeap {
public:
    MaxHeap(int MSize) : MaxSize(MSize) {
        array = new T[MaxSize + 1];
        num = 0;
    }
    ~MaxHeap() {
        delete array;
    }
    bool insert_ele(T item);
    bool delete_ele(T &item);

private:
    int MaxSize;           //max size of heap
    int num;               //number of heap element
    T *array;
    void adjust(int i, int n);
};

template<typename T>
bool MaxHeap<T>::insert_ele(T item) {
    int p = ++num;
    if (p > MaxSize) {
        cout << "heap size exceeded" << endl;
        return false;
    }
    while (p > 1 && array[p / 2] < item) {
        array[p] = array[p / 2];
        p = p / 2;
    }
    array[p] = item;
    return true;
}

template<typename T>
void MaxHeap<T>::adjust(int i, int n) {
    int p = 2 * i;
    int ele = array[i];
    while (p <= n) {
        if (p < n && array[p + 1] > array[p]) {
            ++p;
        }
        if (ele >= array[p]) {
            break;
        }
        array[p / 2] = array[p];
        p = 2 * p;
    }
    array[p / 2] = ele;
} 

template<typename T>
bool MaxHeap<T>::delete_ele(T &item) {
    if (num == 0) {
        cout << "heap is empty" << endl;
        return false;
    }
    item = array[1];
    array[1] = array[num--];
    adjust(1, num);
    return true;
}

int main(void) {
    int maxsize = 3;
    int tmp = maxsize;
    MaxHeap<int> max_heap(maxsize);
    int ele;
    while (tmp--) {
        cout << "input number:";
        cin >> ele;
        assert(max_heap.insert_ele(ele));
    }
    for (int i = 1; i <= maxsize; ++i) {
        assert(max_heap.delete_ele(ele));
        cout << "max ele is " << ele << endl;
    }
    return 0;
}
